UVa/11590 - Prefix lookup/11590.8.cpp

   1 //Accepted
   2 using namespace std;
   3 #include <algorithm>
   4 #include <iostream>
   5 #include <iterator>
   6 #include <sstream>
   7 #include <fstream>
   8 #include <cassert>
   9 #include <climits>
  10 #include <cstdlib>
  11 #include <cstring>
  12 #include <string>
  13 #include <cstdio>
  14 #include <vector>
  15 #include <cmath>
  16 #include <queue>
  17 #include <deque>
  18 #include <stack>
  19 #include <list>
  20 #include <map>
  21 #include <set>
  22
  23 #define D(x) cout << #x " = " << (x) << endl
  24
  25 typedef unsigned long long Int;
  26 const int BUFSIZE = 256;
  27 char buf[BUFSIZE];
  28
  29 int M;
  30 map<string, Int> ans;
  31
  32 struct node{
  33   node * left, * right;
  34   bool end; //is this node a complete prefix?
  35   node(bool e) : end(e) {
  36     left = right = NULL;
  37   }
  38 };
  39
  40 //not used, because I love to waste memory (makes me feel sexy)
  41 void clean(node * n){
  42   if (n == NULL) return;
  43   clean(n->left); clean(n->right);
  44   delete n;
  45 }
  46
  47 Int f(string s, node * n){ //s = string built so far, n = the node we are standing at
  48   Int left = 0, right = 0, ret = 0;
  49   if (n->left != NULL){
  50     left = f(s + "0", n->left);
  51   }
  52   if (n->right != NULL){
  53     right = f(s + "1", n->right);
  54   }
  55   ret += left + right;
  56
  57   if (n->end){
  58     Int howmany;
  59     if (M - s.size() < 64){ //we are safe from overflow
  60       Int x = ((1ULL) << (M - s.size())); //2^(m - |s|)
  61       howmany = x - left - right;
  62     }else{ //2^64 overflows!
  63       Int x = 0;
  64       x = ~x; // (x = ~0ULL) <-> (x = 2^64 - 1)
  65       howmany = x - left - right + 1;
  66     }
  67     ret += howmany;
  68     ans[s] = howmany;
  69   }
  70   return ret;
  71 }
  72
  73 int main(){
  74   int n;
  75   while (scanf("%d%d\n", &n, &M)==2 && !(n == 0 && M == 0)){
  76     ans.clear();
  77     node * root = new node(true);
  78     while (n--){
  79       scanf("%s", buf);
  80       node * cur = root;
  81       for (int i=0; ; ++i){
  82         if (buf[i] == '*'){
  83           cur->end = true;
  84           break;
  85         }
  86         if (buf[i] == '0'){
  87           if (cur->left == NULL) cur->left = new node(false);
  88           cur = cur->left;
  89         }else if (buf[i] == '1'){
  90           if (cur->right == NULL) cur->right = new node(false);
  91           cur = cur->right;
  92         }
  93       }
  94     }
  95
  96     f("", root);
  97
  98     int K;
  99     scanf("%d\n", &K);
 100     while (K--){
 101       scanf("%s", buf);
 102       buf[strlen(buf)-1] = 0; //delete *
 103       Int t = ans[string(buf)];
 104       printf("%llu\n", t);
 105     }
 106     puts("");
 107   }
 108   return 0;
 109 }